package Tree;

public class BinaryTreeDemo {

  public static void main(String[] args) {
//    创建二叉树
    BinaryTree tree = new BinaryTree();

//    创建节点
    HeroNode node1 = new HeroNode(1,"will");
    HeroNode node2 = new HeroNode(2,"okada");
    HeroNode node3 = new HeroNode(3,"kenny");
    HeroNode node4 = new HeroNode(4,"jay");
    HeroNode node5 = new HeroNode(5,"yoh");

    /*
        1
      2   3
         5  4
     */
    node1.setLeft(node2);
    node1.setRight(node3);
    node3.setRight(node4);
    node3.setLeft(node5);
    tree.setRoot(node1);

    System.out.println("前序遍历：");//1 2 3 5 4
    tree.preOrder();

    System.out.println("中序遍历：");//2 1 5 3 4
    tree.infixOrder();

    System.out.println("后序遍历：");//2 5 4 3 1
    tree.postOrder();

//    测试
//    System.out.println("前序遍历查找：");
//    HeroNode node = tree.preOrderSearch(5);
//    if (node != null){
//      System.out.printf("找到了，信息为 no=%d name=%s",node.getNo(),node.getName());
//    }else {
//      System.out.printf("没有找到 no=%d 的英雄",5);
//    }
//
//    System.out.println("中序遍历查找：");
//    HeroNode res1 = tree.infixOrderSearch(5);
//    if (res1 != null){
//      System.out.printf("找到了，信息为 no=%d name=%s",res1.getNo(),res1.getName());
//    }else {
//      System.out.printf("没有找到 no=%d 的英雄",5);
//    }
//
//    System.out.println("后序遍历查找：");
//    HeroNode res2 = tree.postOrderSearch(5);
//    if (res2 != null){
//      System.out.printf("找到了，信息为 no=%d name=%s",res2.getNo(),res2.getName());
//    }else {
//      System.out.printf("没有找到 no=%d 的英雄",5);
//    }

    System.out.println("删除前：");
    tree.preOrder();
    tree.infixOrder();
    tree.postOrder();
    tree.delNode(5);
    System.out.println("删除后：");
    tree.preOrder();// 1 2 3 4
    tree.infixOrder();// 2 1 3 4
    tree.postOrder();// 2 4 3 1
  }
}

//定义二叉树
class BinaryTree{
  private HeroNode root;

  public void setRoot(HeroNode root) {
    this.root = root;
  }

//  前序遍历
  public void preOrder(){
    if (root != null){
      root.preOrder();
    }else {
      System.out.println("二叉树为空，无法遍历");
    }
  }
//  中序遍历
  public void infixOrder(){
    if (root != null){
      root.infixOrder();
    }else {
      System.out.println("二叉树为空，无法遍历");
    }
  }
//  后序遍历
  public void postOrder(){
    if (root != null){
      root.postOrder();
    }else {
      System.out.println("二叉树为空，无法遍历");
    }
  }

//  前序遍历查找
  public HeroNode preOrderSearch(int no){
    if (root != null){
      return root.preOrderSearch(no);
    }else {
      return null;
    }
  }
//  中序遍历查找
  public HeroNode infixOrderSearch(int no){
    if (root != null){
      return root.infixOrderSearch(no);
    }else {
      return null;
    }
  }
//  后序遍历查找
  public HeroNode postOrderSearch(int no){
    if (root != null){
      return root.postOrderSearch(no);
    }else {
      return null;
    }
  }

//  删除节点
  public void delNode(int no){
    if (this.root != null){
      if (this.root.getNo() == no){
        this.root = null;
      }else {
        this.root.delNode(no);
      }
    }else {
      System.out.println("二叉树为空，无法删除");
    }
  }
}

class HeroNode{
  private int no;
  private String name;
  private HeroNode left;
  private HeroNode right;

  public HeroNode(int no, String name) {
    this.no = no;
    this.name = name;
  }

  public int getNo() {
    return no;
  }

  public void setNo(int no) {
    this.no = no;
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public HeroNode getLeft() {
    return left;
  }

  public void setLeft(HeroNode left) {
    this.left = left;
  }

  public HeroNode getRight() {
    return right;
  }

  public void setRight(HeroNode right) {
    this.right = right;
  }

  @Override
  public String toString() {
    return "HeroNode{" +
            "no=" + no +
            ", name='" + name + '\'' +
            '}';
  }

//  前序遍历
  public void preOrder(){
    System.out.println(this);
    if (this.left != null){
      this.left.preOrder();
    }
    if (this.right != null){
      this.right.preOrder();
    }
  }
//  中序遍历
  public void infixOrder(){
    if (this.left != null){
      this.left.infixOrder();
    }
    System.out.println(this);
    if (this.right != null){
      this.right.infixOrder();
    }
  }
//  后序遍历
  public void postOrder(){
    if (this.left != null){
      this.left.postOrder();
    }
    if (this.right != null){
      this.right.postOrder();
    }
    System.out.println(this);
  }

//  前序遍历查找
  public HeroNode preOrderSearch(int no){
    System.out.println("前序~");
    if (this.no == no){
      return this;
    }
    HeroNode node = null;
    if (this.left != null){
      node = this.left.preOrderSearch(no);
    }
    if (node != null){
      return node;
    }
    if (this.right != null){
      node = this.right.preOrderSearch(no);
    }
    return node;
  }
//  中序遍历查找
  public HeroNode infixOrderSearch(int no){

    HeroNode node = null;
    if (this.left != null){
      node = this.left.infixOrderSearch(no);
    }
    if (node != null){
      return node;
    }

    System.out.println("中序~");
    if (this.no == no){
      return this;
    }
    if (this.right != null){
      node = this.right.infixOrderSearch(no);
    }
    return node;
  }
//  后序遍历查找
  public HeroNode postOrderSearch(int no){

    HeroNode node = null;
    if (this.left != null){
      node = this.left.postOrderSearch(no);
    }
    if (node != null){
      return node;
    }
    if (this.right != null){
      node = this.right.postOrderSearch(no);
    }
    if (node != null){
      return node;
    }

    System.out.println("后序~");
    if (this.no == no){
      return this;
    }
    return node;
  }

  public void delNode(int no){
//    如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left = null;并且就返回(结束递归删除)
    if (this.left != null && this.left.no == no){
      this.left = null;
      return;
    }
//    如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right = null;并且就返回(结束递归删除)
    if (this.right != null && this.right.no == no){
      this.right = null;
      return;
    }

//    向左递归
    if (this.left != null){
      this.left.delNode(no);
    }
//    向右递归
    if (this.right != null){
      this.right.delNode(no);
    }
  }
}